package org.example.myleet.p1610;

import java.math.BigDecimal;
import java.util.*;

public class Solution {
    /**
     * 思路：以极角的方式进行排序并通过滑动窗口寻找在同一视角内的点
     * visiblePoints0使用了完整的点模型，比较容易理解
     * 首先针对每个点计算其相对于location的极角，可以想象成是从location发出射线连接到每一个点，以location为极坐标的零点并计算相对location的极角
     * 然后再进行排序，然后有个坑要注意的就是视角是可以随意旋转的，也就是顺时针滑动窗口时即使滑完最后一个点，还可以继续顺时针重新滑过第一个点
     * 因此需要继续再加入一个视角大小的角度内的点以供窗口滑动
     * visiblePoints是visiblePoints0的简化版，只计算角度，忽略掉坐标和距离，空间压缩以及排序加速
     */
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int[] o = new int[]{location.get(0), location.get(1)};
        int coincidePointCount = 0;
        List<Double> degreeList = new ArrayList<>(2 * points.size());
        for (List<Integer> point : points) {
            //计算极角
            int dx = point.get(0) - o[0];
            int dy = point.get(1) - o[1];
            double relativeAngle;
            if (dx == 0) {
                //注意斜率k=无穷大的时候，正切函数是算不出来的，因此要特殊讨论
                if (dy > 0) {
                    relativeAngle = 90;
                } else if (dy < 0) {
                    relativeAngle = 270;
                } else {
                    relativeAngle = 0;
                }
            } else {
                //利用正切函数和反正切函数求出极角大小，以度数为单位
                double tan = (double) dy / (double) dx;
                relativeAngle = Math.toDegrees(Math.atan(tan));
                if (dx < 0) {
                    //注意此时点在第二象限至第三象限内
                    relativeAngle += 180;
                } else {
                    if (dy < 0) {
                        //注意此时点在第四象限内
                        relativeAngle += 360;
                    }
                }
            }
            if (dx == 0 && dy == 0) {
                //如果某个点和location重叠，则不进入滑动窗口检查范围内，而是直接记录起来，这个点可以加入到任何一个视角
                ++coincidePointCount;
            } else {
                //这个点的角度加入到滑动窗口检查范围中
                degreeList.add(relativeAngle);
            }
        }
        //按角度排序
        Collections.sort(degreeList);
        //！！接下来注意这里填坑，注意视角可以转一圈回来继续转，所以需要补充从第一个点开始到一个视角大小的点用于循环滑动窗口
        int n = degreeList.size();
        for (int i = 0; i < n; ++i) {
            double cloneDegree = degreeList.get(i) + 360;
            if (cloneDegree > 360 + angle) {
                //加到多一个视角的点就够了
                break;
            }
            degreeList.add(cloneDegree);
        }
        //上面的预处理完成，下面开始滑动窗口找到最多的视角内的点数目
        int maxCount = 0;
        int l = 0, r = 0;
        //窗口内的点需要的视角之和
        double sumAngle = 0;
        for (int i = 1; i < degreeList.size(); ++i) {
            sumAngle += degreeList.get(i) - degreeList.get(r);
            ++r;
            while (sumAngle > angle) {
                //滑动窗口内的点需要的视角超过了题目给的视角，将窗口中角度最小的点移除直到满足题目给的视角
                sumAngle -= degreeList.get(l + 1) - degreeList.get(l);
                ++l;
            }
            //更新视角内最大的点数目
            maxCount = Math.max(maxCount, r - l + 1);
        }
        //注意补充重叠在location上面的点的数目
        maxCount += coincidePointCount;
        return maxCount;
    }

    public int visiblePoints0(List<List<Integer>> points, int angle, List<Integer> location) {
        int[] o = new int[]{location.get(0), location.get(1)};
        int coincidePointCount = 0;
        List<Point> pointList = new ArrayList<>();
        for (List<Integer> point : points) {
            Point p = new Point(point.get(0), point.get(1), o);
            if (p.distance == 0) {
                ++coincidePointCount;
            } else {
                pointList.add(p);
            }
        }
        pointList.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.relativeAngle.compareTo(o2.relativeAngle) == 0) {
                    return o1.distance - o2.distance;
                }
                if (o1.relativeAngle.compareTo(o2.relativeAngle) < 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });
        List<Point> clonePoints = new ArrayList<>(pointList.size());
        for (Point p : pointList) {
            Point clonePoint = p.clone();
            clonePoint.relativeAngle = clonePoint.relativeAngle.add(BigDecimal.valueOf(360));
            if (clonePoint.relativeAngle.compareTo(BigDecimal.valueOf(360 + angle)) > 0) {
                break;
            }
            clonePoints.add(clonePoint);
        }
        pointList.addAll(clonePoints);
        int maxCount = 0;
        int l = 0, r = 0;
        BigDecimal sumAngle = BigDecimal.ZERO;
        for (int i = 1; i < pointList.size(); ++i) {
            sumAngle = sumAngle.add(pointList.get(i).relativeAngle.subtract(pointList.get(r).relativeAngle));
            ++r;
            while (sumAngle.doubleValue() > angle) {
                sumAngle = sumAngle.subtract(pointList.get(l + 1).relativeAngle.subtract(pointList.get(l).relativeAngle));
                ++l;
            }
            maxCount = Math.max(maxCount, r - l + 1);
        }
        maxCount += coincidePointCount;
        return maxCount;
    }

    static class Point {
        int[] p;
        BigDecimal relativeAngle;
        int distance;

        private Point() {}

        public Point(int x, int y, int[] location) {
            p = new int[]{x, y};
            int dx = x - location[0];
            int dy = y - location[1];
            if (dx == 0) {
                if (dy > 0) {
                    relativeAngle = BigDecimal.valueOf(90);
                } else if (dy < 0) {
                    relativeAngle = BigDecimal.valueOf(270);
                } else {
                    relativeAngle = BigDecimal.valueOf(0);
                }
                distance = dy * dy;
            } else {
                double tan = (double) dy / (double) dx;
                relativeAngle = BigDecimal.valueOf(Math.toDegrees(Math.atan(tan)));
                if (dx < 0) {
                    relativeAngle = relativeAngle.add(BigDecimal.valueOf(180));
                } else {
                    if (dy < 0) {
                        relativeAngle = relativeAngle.add(BigDecimal.valueOf(360));
                    }
                }
                distance = dx * dx + dy * dy;
            }
        }

        @Override
        public Point clone() {
            Point clonePoint = new Point();
            clonePoint.p = new int[]{p[0], p[1]};
            clonePoint.relativeAngle = relativeAngle;
            clonePoint.distance = distance;
            return clonePoint;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Point{");
            sb.append("p=").append(Arrays.toString(p));
            sb.append(", relativeAngle=").append(relativeAngle);
            sb.append(", distance=").append(distance);
            sb.append('}');
            return sb.toString();
        }
    }
}
